In today's high performance data processing systems, virtual memory capabilities increase overall system performance. Generally, these virtual memory data processing systems rely upon sophisticated memory management systems to perform high-speed virtual to physical address translations. As a further performance enhancement, many contemporary data processing systems incorporate one or more address translations caches (ATC), which significantly reduce the amount of time required to perform the address translation. Typically, the ATC stores a predetermined number of address translation descriptors, which are used by the memory management unit (MMU) to map the virtual address space onto a physical address space. The operating system initializes all appropriate logical-to-physical address translation information in the ATC of the MMU. The MMU receives the logical addresses, issued by a central processing unit (CPU), and uses the translation descriptors stored in the ATC to perform the logical to physical address translation.
In order to maximize system performance, the ATC must provide high speed and efficient address translation. Generally, the data processing address translation scheme maps fixed-size blocks of addresses called pages, as opposed to independent logical (virtual) addresses, and thus the unit which performs the translation is commonly referred to as a page address translation cache (PATC). The real or physical address space is divided into a predetermined number of page frames, such that the address translation associates a page frame in the physical address space with a page of logical addresses. Each time the CPU issues a logical address to the MMU for address translation, the logical address is compared with the translation descriptors stored in the PATC to determine whether any PATC entry matches the CPU's logical address. When a hit occurs, the PATC performs the translation, and in so doing, provides the corresponding physical address to an external memory device. When a PATC "miss" occurs, the CPU searches a set of translation tables stored in the memory for the correct translation. Although the number of bus cycles associated with the table look-up, or tablewalk exercise varies, in every case the translation table search results in some performance degradation. Thus, in many applications maximum system performance is determined by the hit ratio in the PATC.
The updating and maintenance of the valid entries in the PATC insures maximum system performance. Typically, the PATC is updated when a "miss" occurs, at which time the required translation descriptor is retrieved from memory and loaded into the PATC. The MMU completes the memory access, translating the address through the PATC. The PATC has a fixed storage capacity, therefore, once the PATC is full, a resident translation descriptor must be discarded in order to load the new translation descriptor. The replacement of valid and recently used translation descriptors with the required (new) descriptor may substantially reduce the hit ratio in the PATC, therefore, the determination of the optimal entry for replacement is critical to system performance.
In the prior art, the four most common replacement algorithms are the least recently used (LRU), not last used (NLU), first in first out (FIFO), and random. In order to maintain the LRU policy, a set of LRU registers maintain the current LRU line which is updated based upon the number of cache accesses. Similarly, maintenance of the NLU policy, requires a set of NLU registers to maintain the current NLU line which is updated based upon the number of cache accesses. Consequently, the implementation of the LRU and NLU replacement generally requires additional logic circuitry, therefore, in some applications, the use of the LRU and NLU replacement methods is not feasible. Random replacement algorithms, while easy to implement, often fail to provide the optimum system performance. The actual performance degradation associated with random replacement is a function of the application. In general, random replacement algorithms fail to deliver the performance of the LRU and NLU algorithms. The FIFO replacement algorithm is easy to implement, and requires minimal silicon area. Typically, a shift register pointer indicates a particular entry (entry number zero at reset) at all times until a PATC miss occurs. Once the miss occurs, the PATC entry denoted is replaced by the new entry, and the register is shifted to point to the next entry, and so on in a circular fashion. Thus, the shift register is not shifted again until another PATC miss occurs. Accordingly, valid and frequently used descriptors may be overwritten using the FIFO replacement method.